#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
const int MOD=2333333;
struct Mat{
    ll m[3][3];
    Mat operator *(Mat &rhs){
        Mat ans;
        memset(ans.m,0,sizeof(ans.m));
        for(int k=0;k<3;k++){
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++){
                    ans.m[i][j]=(ans.m[i][j]+(m[i][k]%MOD*rhs.m[k][j]%MOD)%MOD)%MOD;
                }
            }
        }
        return ans;
    }

    Mat operator ^(int n){
        Mat ans;
        memset(ans.m,0,sizeof(ans.m));
        ans.m[0][0]=ans.m[1][1]=ans.m[2][2]=1;
        while(n){
            if(n%2){
                ans=ans*(*this);
            }
            n/=2;
            (*this)=(*this)*(*this);
        }
        return ans;
    }
};
int main(void){
    while(~scanf("%lld%lld",&n,&k)){
        Mat t;
        memset(t.m,0,sizeof(t));
        t.m[0][0]=t.m[0][1]=t.m[1][1]=t.m[1][2]=t.m[2][1]=1;
        Mat a;
        memset(a.m,0,sizeof(a.m));
        a.m[0][0]=2;
        a.m[1][0]=1;
        a.m[2][0]=1;
        // for(int i=0;i<3;i++){
        //     for(int j=0;j<3;j++){
        //         printf("%d ",t.m[i][j]);
        //     }
        //     printf("\n");
        // }
        Mat g=(t^(n-1))*a;
        //printf("%d %d %d\n",g.m[0][0],g.m[1][0],g.m[2][0]);
        ll ans=(g.m[1][0]%MOD*g.m[2][0]%MOD)%MOD+n*k*k+2*k*((g.m[0][0]-1)%MOD)%MOD;
        printf("%lld\n",ans%MOD);
    }
    return 0;
}